#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<int> ret;
    int mergesort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return 0;

        int mid = (left + right) / 2;
        int l = mergesort(nums, left, mid);
        int r = mergesort(nums, mid + 1, right);

        int c = 0;
        for (int y = left, z = mid + 1; y <= mid; y++)
        {
            while (z <= right && nums[y] > nums[z]) z++;
            c += z - mid - 1;
        }
        int i = left, a = left, b = mid + 1;
        while (a <= mid && b <= right) ret[i++] = nums[a] < nums[b] ? nums[a++] : nums[b++];
        while (a <= mid) ret[i++] = nums[a++];
        while (b <= right) ret[i++] = nums[b++];
        for (int x = left; x <= right; x++) nums[x] = ret[x];

        return l + r + c;
    }
    int reversePairs(vector<int>& record) {
        ret.resize(record.size());
        return mergesort(record, 0, record.size() - 1);
    }
};
